CODE 92. First Missing Positive

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/10/28/2013-10-28-CODE 92 First Missing Positive/

访问原文「CODE 92. First Missing Positive」

Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.

public int firstMissingPositive(int[] A) {
	// Start typing your Java solution below
	// DO NOT write main() function
	ArrayList<Integer> numbers = new ArrayList<Integer>();
	for (int i = 0; i < A.length; i++) {
		numbers.add(i + 1);
	}
	for (int i = 0; i < A.length; i++) {
		if (numbers.contains((Integer) A[i])) {
			numbers.remove((Integer) A[i]);
		}
	}
	if (numbers.isEmpty()) {
		return A.length + 1;
	} else {
		return numbers.get(0);
	}
}